Our goal is to organize the keys in a binary search tree so that the average time it takes to locate a key is minimized. In general, we cannot find an optimal binary search tree by considering all binary search trees because the number of such tree is at least exponential in n.
최적이진탐색트리 알고리즘의 목적은 Key를 찾는데 걸리는 평균시간이 최소화되도록 이진탐색트리의 Key를 구성하는 것이다.
Example Shows the five different trees when n = 3. The actual values of the keys are not important. The only requirement is that they be ordered. $p_i$ is the probability that $Key_i$ is the search key. If
$p_1$ = 0.7 ($Key_1$ 찾을 확률), $p_2$ = 0.2 ($Key_2$ 찾을 확률), and $p_3$ = 0.1 ($Key_3$ 찾을 확률),
the average search times for the below trees are:
| 트리번호 | 평균검색시간 | 평균검색시간 설명 |
|---|---|---|
| 1 | 3(0.7) ＋ 2(0.2) ＋ 1(0.1) = 2.6 | Key1을 세번 비교 후 찾을 확률 ＋ Key2를 두번 비교 후 찾을 확률 ＋ Key3를 한번 비교 후 찾을 확률. |
| 2 | 2(0.7) ＋ 3(0.2) ＋ 1(0.1) = 2.1 | … |
| 3 | 2(0.7) ＋ 1(0.2) ＋ 2(0.1) = 1.8 | Key1을 두번 비교 후 찾을 확률 ＋ Key2를 한번 비교 후 찾을 확률 ＋ Key3를 두번 비교 후 찾을 확률. |
| 4 | 1(0.7) ＋ 3(0.2) ＋ 2(0.1) = 1.5 | … |
| 5 | 1(0.7) ＋ 2(0.2) ＋ 3(0.1) = 1.4 | Key1을 한번 비교 후 찾을 확률 ＋ Key2를 두번 비교 후 찾을 확률 ＋ Key3를 세번 비교 후 찾을 확률. |
![[The possible binary trees when there are three keys.]](/images/algo/optm-binsearch-tree_figure.png)
The fifth tree is optimal. |
$Key_1, Key_2, Key_3$로 구성된 트리 자료구조에서 사용자가 $Key_1$ 값을 검색하러 올 확률이 70%, $Key_2$ 값은 20%, $Key_3$ 값은 10%라고 하자. (이진탐색트리 특성에 따라, $Key_1 \le Key_2 \le Key_3$)
3개의 $Key$값으로 이진탐색트리를 구성하는 방법은 총 5가지이며, 이 중에서 5번 모양이 평균검색시간을 고려했을 때 최적화된 이진탐색트리이다. 트리의 균형이 깨지더라도 $Key_1$을 찾을 확률이 높으므로 $Key_1$을 루트로 둔다.
Example Suppose we have three keys and the probabilities in this above Example. To determine A[2][3] we must consider the two trees. For those two trees we have the following:
| 트리번호 | 평균검색시간 | 평균검색시간 설명 |
|---|---|---|
| 1 | 1(p2) ＋ 2(p3) = 1(0.2) ＋ 2(0.1) = 0.4 | Key2를 한번 비교 후 찾을 확률 ＋ Key3를 두번 비교 후 찾을 확률. |
| 2 | 2(p2) ＋ 1(p3) = 2(0.2) ＋ 1(0.1) = 0.5 | Key2를 두번 비교 후 찾을 확률 ＋ Key3를 한번 비교 후 찾을 확률. |
![[The binary search trees composed of Key2 and Key3.]](/images/algo/optm-binsearch-tree_figure1.png)
The first tree is optimal, and A[2][3] = 0.4. |
A[2][3]이란 $Key_2$와 $Key_3$으로 구성된 이진탐색트리의 최적화된 평균검색시간이다. 최적화된 평균검색시간을 갖는 트리 구성을 하려면 위의 1번 트리처럼 $Key_2$를 루트에 놓아야 한다.
Optimal Binary Search Tree Algorithm
Algorithm Design
The average search time for tree k is given by,
![[Optimal binary search tree given that $Key_k$ is at the root.]](/images/algo/optm-binsearch-tree.png)
$$
\underbrace{A[1][k-1]} + \underbrace{p_1 + \cdots + p_{k-1}} + \underbrace{p_k} + \underbrace{A[k+1][n]} + \underbrace{p_{k+1} + \cdots + p_n}
$$
| $A[1][k-1]$ | Average time in left subtree |
| $p_1 + \cdots + p_{k-1}$ | Additional time comparing at root |
| $p_k$ | Average time searching for root |
| $A[k+1][n]$ | Average time in right subtree |
| $p_{k+1} + \cdots + p_n$ | Additional time comparing at root |
which equals
$$
A[1][k-1] + A[k+1][n] + \sum_{m=1}^np_m
$$
Because one of the k trees must be optimal, the average search time for optimal tree is given by
$$
A[1][n] = minimum_{1 \le k \le n}(A[1][k-1] + A[k+1][n]) + \sum_{m=1}^np_m,
$$
$$
\begin{cases}
A[i][j] = minimum_{i \le k \le j}(A[i][k-1] + A[k+1][j]) + \sum_{m=i}^jp_m \quad i < j \\
A[i][i] = p_i \\
A[i][i-1] \ \text{and} \ A[j+1][j] \ \text{are defined to be 0}.
\end{cases}
$$
A[1][k-1]은 $Key_1, \cdots, Key_{k-1}$로 구성된 왼쪽 부분트리의 최적화된 평균검색시간이다. A[k+1][n] 역시 마찬가지로 $Key_{k+1}, \cdots, Key_n$으로 구성된 오른쪽 부분트리의 최적화된 평균검색시간을 뜻한다.
식이 복잡해 보일수도 있지만 사실 그렇지 않다. (왼쪽 부분트리에서의 평균검색시간) + (루트에서의 검색시간) + (오른쪽 부분트리에서의 평균검색시간)으로 이루어진 직관적인 수식이다.
Pseudo Code
void optsearchtree(int n, const float p[], float& minavg, index R[][]) |
Source Code
// File: optbintree.h |
// File: optbintree.cpp |
// File: optbintreetest.cpp |
Time Complexity Analysis
Basic operation
- The instructions executed for each value of k.
Input size
- n, the number of keys.
Every-Case Time Complexity
- $T(n) = \sum_{diagonal=1}^{n-1}[(n-diagonal) \times (diagonal+1)] = \frac{n(n-1)(n+4)}{6} \in \Theta(n^3)$
| 루프구분 | 루프조건 | 수행 횟수 |
|---|---|---|
| diagonal-loop 수행 횟수: | 1 to n-1 | n-1 |
| i－loop 수행 횟수: | 1 to n-diagonal | n－diagonal |
| k－loop 수행 횟수: | i to j | j － i ＋ 1 = (i ＋ diagonal) - i + 1 = diagonal + 1 |
| ※ j = i ＋ diagonal |
Optimization Problem
주어진 문제에 대하여 하나 이상의 많은 해답이 존재할 때, 이 가운데에서 가장 최적인 해답(optimal solution)을 찾아야 하는 문제를 최적화문제(optimization problem)라고 한다. 최적이진탐색트리 문제는 최적화문제에 속한다.
Principle of Optimality
플로이드, 연쇄행렬곱셈과 마찬가지로 최적이진탐색트리의 부분 해는 최적 해를 구성하는 일부임을 알 수 있다. 따라서 최적이진탐색트리 역시 최적의 원칙을 만족하게 되며, 동적계획법을 사용하여 문제를 풀 수 있다.
Dynamic Programming Exercises
Create the optimal binary search tree for the following items, where the probability occurrence of each word is given in parentheses:
CASE (0.05), ELSE (0.15), END (0.05), IF (0.35), OF (0.05), THEN (0.35).
다음은 책에 있는 연습문제를 알고리즘에 적용한 결과이다. 생성된 이진탐색트리를 출력할 때 재귀를 이용해서 출력했다. IF가 루트 ELSE는 IF의 왼쪽자식, TEHN이 IF의 오른쪽 자식이다.
index 1 2 3 4 5 6 |